package com.javabasic.algorithm.leetcode;

public class N_thTribonacciNumber {

    private int[] dp = new int[38];


    public int tribonacci(int n) {
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 1;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
        }
        return dp[n];
    }

    /**
     * 递归解法  太慢了 有太多重复计算的了
     * @param n
     * @return
     */
    public int recursionSolution(int n) {
        if (n == 0) return 0;
        if (n == 1 || n== 2) return 1;
        return tribonacci(n-1) + tribonacci(n-2) + tribonacci(n-3);
    }

    /**
     * 记忆化递归解法  将计算的结果存入dp数组 然后就不用重复计算了【只要dp数组值不为0就表示这个值在之前计算过直接返回dp[n]就可以了】
    * @param n
     * @return
     */
    public int recursionSolutionOfMemory(int n) {
        if (n == 0) return 0;
        if (n == 1 || n== 2) return 1;
        if (dp[n] != 0) return dp[n];
        dp[n] = tribonacci(n-1) + tribonacci(n-2) + tribonacci(n-3);
        return dp[n];
    }


}